#pragma once

#include <iostream>
#include <assert.h>
#include <vector>
#include <string>
using namespace std;


namespace xsc 
{
	//节点
	template<typename T>
	struct List_node
	{
		T _data;
		List_node<T>* _prev;
		List_node<T>* _next;

		List_node(const T& val = T())
			:_data(val)
			,_prev(nullptr)
			,_next(nullptr)
		{}

		template<typename...Args>
		List_node(Args&&...args)
			:_data(std::forward<Args>(args)...)
			, _prev(nullptr)
			, _next(nullptr)
		{}
	};

	//iterator
	template <typename T, typename Ref ,typename Ptr>
	struct List_iterator
	{
		typedef struct List_node<T> node;
		typedef struct List_iterator<T,Ref,Ptr> Self;
		node* _node;

		List_iterator(node* node) :
			_node(node)
		{}


		Ref operator*()
		{
			return _node->_data;
		}

		Self& operator++()
		{
			_node = _node->_next;

			return *this;
		}

		Self& operator--()
		{
			_node = _node->_prev;

			return *this;
		}

		Self& operator++(int)
		{
			Self tmp(*this);

			_node = _node->_next;

			return tmp;
		}

		Self& operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

		bool operator==(const Self& s)
		{
			return _node == s._node;
		}
	};

	//链表
	template<typename T>
	class list
	{
		typedef struct List_node<T> node;

	public:
		typedef struct List_iterator<T,T&,T*> iterator;
		typedef struct List_iterator<T,const T&,const T*> const_iterator;



		void emptyinit()
		{
			_head = new node;
			_head->_prev = _head;
			_head->_next = _head;

			_size = 0;
		}

		list()
		{
			emptyinit();
		}

		list(const list<T>& t)
		{
			emptyinit();

			for (auto& e : t)
			{
				push_back(e);
			}
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void swap(list<T>& t)
		{
			std::swap(_head, t._head);
			std::swap(_size, t._size);
		}

		list<T>& operator==(list<T> t)
		{
			swap(t);
			return *this;
		}

		void clear()
		{
			auto iter = begin();
			while (begin() != end())
			{
				iter = erase(iter);
			}
		}

		iterator begin()
		{
			return _head->_next;
		}

		iterator end() 
		{
			return _head;
		}

		const_iterator begin() const
		{
			return _head->_next;
		}

		const_iterator end() const
		{
			return _head;
		}

		//void push_back(const T& val)
		//{
		//	insert(end(), val);
		//}

		//void push_back(const T&& val)
		//{
		//	insert(end(), val);
		//}

		//万能引用
		template<typename T>
		void push_back(T&& val)
		{
			insert(end(), forward<T>(val));
		}

		template<typename...Args>
		void emplace_back(Args&&...args)
		{
			insert(end(), std::forward<Args>(args)...);
		}


		void push_front(const T& val)
		{
			insert(begin(), val);
		}

		template<typename...Args>
		iterator insert(iterator p, const Args&& ...args)
		{
			node* newnode = new node(std::forward<Args>(args)...);

			node* prev = p._node->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;

			newnode->_next = p._node;
			p._node->_prev = newnode;

			++_size;

			return newnode;
		}

		iterator insert(iterator p, const T& val)
		{
			node* newnode = new node(val);
			
			node* prev = p._node->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;

			newnode->_next = p._node;
			p._node->_prev = newnode;

			++_size;

			return newnode;
		}

		iterator erase(iterator p)
		{
			assert(p != end());

			node* prev = p._node->_prev;
			node* next = p._node->_next;

			prev->_next = next;
			next->_prev = prev;

			delete p._node;
			p._node = nullptr;
			--_size;

			return next;
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

	private:
		node* _head;
		size_t _size;
	};
}